package com.apkcore.bl;

public class _最长子串 {
    public static void main(String[] args) {
        String text1 = "ABCD", text2 = "BABC";
        System.out.println(new _最长子串().test(text1, text2));
    }

    /**
     * 优化可以知道，在二维数组里，只使用到了dp[i-1][j-1],我们可以使用一个一维数组以及临时变量leftTop来保存，
     * 但是只要细心我们可以进一步优化，从后往前遍历时，一维数组里dp[j-1]就是没有改变的，也就是leftTop
     */
    private int test(String text1, String text2) {
        if (text1 == null || text2 == null) {
            return 0;
        }
        char[] char1 = text1.toCharArray();
        char[] char2 = text2.toCharArray();

        char[] rowArr = char1;
        char[] colArr = char2;
        if(char1.length<char2.length){
            rowArr = char2;
            colArr = char1;
        }

        int[] dp = new int[colArr.length + 1];

        // dp[i][j]定义为
        int max = 0;
        for (int i = 1; i <= rowArr.length; i++) {
            for (int j = colArr.length; j >= 1; j--) {
                if (rowArr[i - 1] == colArr[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                    max = Math.max(max, dp[j]);
                } else {
                    dp[j] = 0;
                }
                System.out.print(dp[j] + ", ");
            }
            System.out.println();
        }
        return max;
    }

    /**
     * dp[i][j]定义为以text1第i个值结尾与text2第j个结尾的公共子串长度
     * 初始化dp[i][0]=0 dp[0][j] = 0
     * 当text[i-1]！=text[j-1]时，dp[i][j]=0
     * 否则，说明只要看前dp[i-1][j-1]+1
     */
    private int test1(String text1, String text2) {
        if (text1 == null || text2 == null) {
            return 0;
        }
        char[] char1 = text1.toCharArray();
        char[] char2 = text2.toCharArray();
        int[][] dp = new int[char1.length + 1][char2.length + 1];

        int max = 0;
        for (int i = 1; i <= char1.length; i++) {
            for (int j = 1; j <= char2.length; j++) {
                if (char1[i - 1] == char2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    max = Math.max(max, dp[i][j]);
//                } else {
//                    dp[i][j] = 0;
                }
                System.out.print(dp[i][j] + ", ");
            }
            System.out.println();
        }
        return max;
    }

}
